package arrayandstring;

import java.util.Arrays;
/**
 * https://leetcode-cn.com/problems/valid-anagram/
 */
public class E242_ValidAnagram {
    /**
     * 官方解法
     * 时间复杂度 O(nlogn) 空间复杂度 O(n)
     * 将字符串转换为char[]数组在对数组内容排序
     * 比较排序后的两个数组内容是否相等
     */
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();
        Arrays.sort(sChar);
        Arrays.sort(tChar);
        return Arrays.equals(sChar, tChar);
    }
    /**
     * 时间复杂度 O(n) 空间复杂度 O(n)
     * 重要的前提“字符串仅包含小写字母”
     * 维护一个count[]数组记录每个字母出现的次数
     * 一加一减后数组元素是否为0
     */
    public static boolean isAnagram1(String s, String t) {
        int counts[] = new int[26];
        for (char i : s.toCharArray()) {
            ++counts[i-'a'];
        }
        for (char i : t.toCharArray()) {
            --counts[i-'a'];
        }
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        isAnagram1("rat", "car");
    }
}
